package com.hot100;

import java.util.HashMap;
import java.util.LinkedHashMap;

public class Solution146 {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.get(1);
        lruCache.put(3,3);
        lruCache.get(2);
        lruCache.put(4,4);
    }
}


class LRUCache {

    class Node {
        int key;
        int val;
        Node pre;
        Node next;
        Node() {

        }
        Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    int cap;
    Node head;
    Node tail;
    HashMap<Integer, Node> map;

    LRUCache(int capacity) {
        this.cap = capacity;
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
        map = new HashMap<>();
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        makeRecent(key);
        return map.get(key).val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            makeRecent(key);
            map.get(key).val = value;
            return;
        }
        if (map.size() >= cap) {
            map.remove(head.next.key);
            head.next.key = key;
            head.next.val = value;
            map.put(key, head.next);
            makeRecent(key);
            return;
        }
        Node node = new Node(key, value);
        node.pre = tail.pre;
        node.next = tail;
        tail.pre.next = node;
        tail.pre = node;
        map.put(key, node);
    }

    private void makeRecent(int key) {
        Node node = map.get(key);
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre = tail.pre;
        node.next = tail;
        tail.pre.next = node;
        tail.pre = node;
    }

}